{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Search a 2D Matrix II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #divide-and-conquer #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #分治 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: searchMatrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #搜索二维矩阵 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>编写一个高效的算法来搜索&nbsp;<code><em>m</em>&nbsp;x&nbsp;<em>n</em></code>&nbsp;矩阵 <code>matrix</code> 中的一个目标值 <code>target</code> 。该矩阵具有以下特性：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每行的元素从左到右升序排列。</li>\n",
    "\t<li>每列的元素从上到下升序排列。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>示例 1：</b></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/11/25/searchgrid2.jpg\" />\n",
    "<pre>\n",
    "<b>输入：</b>matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5\n",
    "<b>输出：</b>true\n",
    "</pre>\n",
    "\n",
    "<p><b>示例 2：</b></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/11/25/searchgrid.jpg\" />\n",
    "<pre>\n",
    "<b>输入：</b>matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20\n",
    "<b>输出：</b>false\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == matrix.length</code></li>\n",
    "\t<li><code>n == matrix[i].length</code></li>\n",
    "\t<li><code>1 &lt;= n, m &lt;= 300</code></li>\n",
    "\t<li><code>-10<sup>9</sup>&nbsp;&lt;= matrix[i][j] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li>每行的所有元素从左到右升序排列</li>\n",
    "\t<li>每列的所有元素从上到下升序排列</li>\n",
    "\t<li><code>-10<sup>9</sup>&nbsp;&lt;= target &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [search-a-2d-matrix-ii](https://leetcode.cn/problems/search-a-2d-matrix-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [search-a-2d-matrix-ii](https://leetcode.cn/problems/search-a-2d-matrix-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]\\n5', '[[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]\\n20']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        height = len(matrix)\n",
    "        width = 0\n",
    "        for samp in matrix[0]:\n",
    "            width += 1\n",
    "        i = 0\n",
    "        while i < height:\n",
    "            if target > matrix[i][width-1]:\n",
    "                del matrix[i]\n",
    "                height = len(matrix)\n",
    "            elif target == matrix[i][width-1]:\n",
    "                return True\n",
    "            else:\n",
    "                i += 1\n",
    "        if matrix == []:\n",
    "            return False\n",
    "        i = 0\n",
    "        while i < width:\n",
    "            if target > matrix[height-1][i]:\n",
    "                for j in range(height):\n",
    "                    del matrix[j][i]\n",
    "                    width = 0\n",
    "                    for samp in matrix[0]:\n",
    "                        width += 1\n",
    "            elif target == matrix[height-1][i]:\n",
    "                return True\n",
    "            else:\n",
    "                i += 1\n",
    "        if matrix == []:\n",
    "            return False\n",
    "        for sonl in matrix:\n",
    "            for soni in sonl:\n",
    "                if target == soni:\n",
    "                    return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        # 不能双重二分，因为会导致某个维度上的target被跳过，而没有搜索到（假设目标值19）\n",
    "        # 固定x维，去对y维进行二分\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        x = m - 1\n",
    "        for i in range(m):\n",
    "            if matrix[i][0] > target:\n",
    "                x = i - 1\n",
    "\n",
    "        for i in range(x + 1):\n",
    "            left, right = -1, n\n",
    "            while left + 1 < right:\n",
    "                mid = (left + right) // 2\n",
    "                if matrix[i][mid] == target:\n",
    "                    return True\n",
    "                elif matrix[i][mid] > target:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        row, column = 0, len(matrix[0]) - 1\n",
    "        while column >= 0 and row < len(matrix):\n",
    "            if matrix[row][column] > target:\n",
    "                column -= 1\n",
    "            elif matrix[row][column] < target:\n",
    "                row += 1\n",
    "            else:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        i, j = 0, len(matrix[0]) - 1\n",
    "        while i < len(matrix) and j >= 0:\n",
    "            if matrix[i][j] == target:\n",
    "                return True\n",
    "            elif matrix[i][j] < target:\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        height = len(matrix)\n",
    "        width = 0\n",
    "        for samp in matrix[0]:\n",
    "            width += 1\n",
    "        i = 0\n",
    "        while i < height:\n",
    "            if target > matrix[i][width-1]:\n",
    "                del matrix[i]\n",
    "                height = len(matrix)\n",
    "            elif target == matrix[i][width-1]:\n",
    "                return True\n",
    "            else:\n",
    "                i += 1\n",
    "        if matrix == []:\n",
    "            return False\n",
    "        i = 0\n",
    "        while i < width:\n",
    "            if target > matrix[height-1][i]:\n",
    "                for j in range(height):\n",
    "                    del matrix[j][i]\n",
    "                    width = 0\n",
    "                    for samp in matrix[0]:\n",
    "                        width += 1\n",
    "            elif target == matrix[height-1][i]:\n",
    "                return True\n",
    "            else:\n",
    "                i += 1\n",
    "        if matrix == []:\n",
    "            return False\n",
    "        for sonl in matrix:\n",
    "            for soni in sonl:\n",
    "                if target == soni:\n",
    "                    return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        x, y = 0, n -1\n",
    "        while x < m and y >= 0:\n",
    "            if matrix[x][y] == target:\n",
    "                return True\n",
    "            \n",
    "            if matrix[x][y] > target:\n",
    "                y -= 1\n",
    "            else:\n",
    "                x += 1\n",
    "                \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix, target: int) -> bool:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        def dfs(matrix, i, j):\n",
    "            if i < 0 or i >= m or j < 0 or j >= n or matrix[i][j] == 'inf':\n",
    "                return False\n",
    "            if matrix[i][j] == target:\n",
    "                matrix[i][j] = 'inf'\n",
    "                return True\n",
    "            elif matrix[i][j] > target:\n",
    "                matrix[i][j] = 'inf'\n",
    "                d1 = dfs(matrix, i - 1, j)\n",
    "                d2 = dfs(matrix, i, j - 1)\n",
    "            else:\n",
    "                matrix[i][j] = 'inf'\n",
    "                d1 = dfs(matrix, i + 1, j)\n",
    "                d2 = dfs(matrix, i, j + 1)\n",
    "            return d1 or d2\n",
    "        return dfs(matrix, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        i = 0\n",
    "        j = len(matrix[0])-1\n",
    "        while i < len(matrix) and j >=0:\n",
    "            if matrix[i][j] > target:\n",
    "                j -= 1\n",
    "            elif matrix[i][j] < target:\n",
    "                i += 1\n",
    "            else:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        # O(m*logn)\n",
    "        for i in range(m):\n",
    "            left, right = 0, n - 1\n",
    "            while left <= right:\n",
    "                mid = left + ((right - left) >> 1)\n",
    "                if matrix[i][mid] == target:\n",
    "                    return True\n",
    "                if matrix[i][mid] > target:\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        i, j = 0, n-1\n",
    "        while i < m and j >= 0:\n",
    "            if matrix[i][j] == target:\n",
    "                return True\n",
    "            elif matrix[i][j] > target:\n",
    "                j -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        m = len(matrix)\n",
    "        n =len(matrix[0])\n",
    "        i, j = 0, 0\n",
    "\n",
    "        \n",
    "        while matrix[i][j] < target:\n",
    "            if i == m-1 and j == n-1:\n",
    "                return False\n",
    "            if i < m - 1:\n",
    "                i += 1\n",
    "            if j < n - 1:\n",
    "                j += 1\n",
    "            \n",
    "        if matrix[i][j] == target:\n",
    "            return True\n",
    "        oi = i\n",
    "        oj = j\n",
    "        i -= 1\n",
    "        while i >= 0 and j < n:\n",
    "            if matrix[i][j] == target:\n",
    "                return True\n",
    "            elif matrix[i][j] < target:\n",
    "                j += 1\n",
    "            else:\n",
    "                i -= 1\n",
    "        oj -= 1\n",
    "        while oj >= 0 and oi < m:\n",
    "            if matrix[oi][oj] == target:\n",
    "                return True\n",
    "            elif matrix[oi][oj] < target:\n",
    "                oi += 1\n",
    "            else:\n",
    "                oj -= 1\n",
    "            \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        m = len(matrix)\n",
    "        i, j = 0, len(matrix[0])-1\n",
    "        while i < m and j > -1:\n",
    "            if target == matrix[i][j]:\n",
    "                return True\n",
    "            elif target > matrix[i][j]:\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        i, j = m-1, 0\n",
    "        while i>=0 and j<n:\n",
    "            if matrix[i][j]==target:\n",
    "                return True\n",
    "            elif matrix[i][j]<target:\n",
    "                j += 1\n",
    "            else:\n",
    "                i -= 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        x, y = 0, n-1\n",
    "        while True:\n",
    "            if x >= m or y < 0:\n",
    "                return False\n",
    "            if matrix[x][y] < target:\n",
    "                x += 1\n",
    "            elif matrix[x][y] > target:\n",
    "                y -= 1\n",
    "            else:\n",
    "                return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if not matrix or not matrix[0]:\n",
    "            return False\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        row, col = m - 1, 0\n",
    "        while row >= 0 and col < n:\n",
    "            if matrix[row][col] == target:\n",
    "                return True\n",
    "            elif matrix[row][col] > target:\n",
    "                row -= 1\n",
    "            else:\n",
    "                col += 1\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if not matrix: return 0\n",
    "        i = len(matrix)-1\n",
    "        while i >= 0:\n",
    "            if target < matrix[i][0]:\n",
    "                i -= 1\n",
    "            else:\n",
    "                if target in matrix[i]:return True\n",
    "                else: i-= 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        m = len(matrix)\n",
    "        if m == 0:\n",
    "            return False\n",
    "        n = len(matrix[0])\n",
    "        i = m - 1\n",
    "        j = 0\n",
    "\n",
    "        while i >= 0 and j < n:\n",
    "            if matrix[i][j] == target:\n",
    "                return True\n",
    "            if matrix[i][j] > target:\n",
    "                i -= 1\n",
    "            else:\n",
    "                j += 1\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix, target):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :type target: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    " \n",
    "        if len(matrix) == 0:\n",
    "            return False\n",
    "        row = len(matrix)\n",
    "        col = len(matrix[0])\n",
    "        i = 0\n",
    "        j = col - 1\n",
    "        while i < row and j >= 0 :\n",
    "            if matrix[i][j] == target:\n",
    "                return True\n",
    "            elif matrix[i][j] > target:\n",
    "                j -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if not matrix:\n",
    "            return False\n",
    "        row_max=len(matrix)-1\n",
    "        col_max=len(matrix[0])-1\n",
    "\n",
    "        cur_row=row_max\n",
    "        cur_col=0\n",
    "\n",
    "        current=matrix[cur_row][cur_col]\n",
    "\n",
    "        while 1:\n",
    "            if current==target:\n",
    "                return True\n",
    "            elif target<current:\n",
    "                if cur_row>0:\n",
    "                    cur_row-=1\n",
    "                    current=matrix[cur_row][cur_col]\n",
    "                else:\n",
    "                    return False\n",
    "            elif target>current:\n",
    "                if cur_col<col_max:\n",
    "                    cur_col+=1\n",
    "                    current=matrix[cur_row][cur_col]\n",
    "                else:\n",
    "                    return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        shortDim = min(m,n)\n",
    "        for i in range(shortDim):\n",
    "            rowFound = self.binarySearchRow(matrix,i,target)\n",
    "            colFound = self.binarySearchCol(matrix,i,target)\n",
    "\n",
    "            if rowFound or colFound:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "    def binarySearchRow(self,matrix,row,target):\n",
    "        left=row\n",
    "        right=len(matrix[0])-1\n",
    "        while left<=right:\n",
    "            mid=left+(right-left)//2\n",
    "            if matrix[row][mid]==target:\n",
    "                return True\n",
    "            elif matrix[row][mid]<target:\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid-1\n",
    "        return False\n",
    "\n",
    "    def binarySearchCol(self,matrix,col,target):\n",
    "        left=col\n",
    "        right=len(matrix)-1\n",
    "        while left<=right:\n",
    "            mid = left+(right-left)//2\n",
    "            if matrix[mid][col]==target:\n",
    "                return True\n",
    "            elif matrix[mid][col]<target:\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid-1\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\r\n",
    "        m, n = len(matrix), len(matrix[0])\r\n",
    "        row, col = 0, n - 1\r\n",
    "        while row < m and col >= 0:\r\n",
    "            if matrix[row][col] == target:\r\n",
    "                return True\r\n",
    "            elif matrix[row][col] < target:\r\n",
    "                row += 1\r\n",
    "            else:\r\n",
    "                col -= 1\r\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "\n",
    "        column = len(matrix[0])-1\n",
    "\n",
    "        rowid = len(matrix)-1\n",
    "        columid = 0\n",
    "\n",
    "        while rowid >=0 and columid <= column:\n",
    "            print(matrix[rowid][columid])\n",
    "            if matrix[rowid][columid] == target:\n",
    "                return True\n",
    "            \n",
    "            if matrix[rowid][columid] >= target:\n",
    "                rowid -= 1\n",
    "            else:\n",
    "                columid += 1\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix, target: int) -> bool:\n",
    "        root = matrix[0][-1]\n",
    "        while root!=target:\n",
    "            if target>root:\n",
    "                matrix = matrix[1:]\n",
    "            elif target < root:\n",
    "                matrix = [row[:-1] for row in matrix]\n",
    "            else:\n",
    "                #print('????')\n",
    "                return True\n",
    "            #print(matrix)\n",
    "            #tmp =\n",
    "            if not any(matrix):return False\n",
    "\n",
    "            root = matrix[0][-1]\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        mtx=matrix\n",
    "        while mtx and mtx[0]:\n",
    "            #print(mtx)\n",
    "            n=len(mtx)-1\n",
    "            #print(n,mtx[n][0],target)\n",
    "            if mtx[n][0]==target:           \n",
    "                #print(\"true\")     \n",
    "                return True\n",
    "                #break\n",
    "            elif mtx[n][0]>target:\n",
    "                mtx=mtx[:-1]\n",
    "            else:\n",
    "                for i in range(len(mtx)):\n",
    "                    tmp=mtx[i]\n",
    "                    tmp=tmp[1:]\n",
    "                    mtx[i]=tmp\n",
    "            \n",
    "\n",
    "        return False\n",
    "\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        def search(r1, r2, c1, c2):\n",
    "            # print(r1, r2, c1, c2)\n",
    "            nonlocal target\n",
    "            if r1 > r2 or c1 > c2: return False\n",
    "            if (r2-r1+1) * (c2-c1+1) <= 16:\n",
    "                for i in range(r1, r2 +1):\n",
    "                    for j in range(c1, c2+1):\n",
    "                        if matrix[i][j] == target:\n",
    "                            return True\n",
    "                return False\n",
    "            mid_r = (r1+r2)//2\n",
    "            mid_c = (c1+c2)//2\n",
    "            # print('mid:', mid_r, mid_c)\n",
    "            if matrix[mid_r][mid_c] == target: return True\n",
    "            if matrix[mid_r][mid_c] > target:\n",
    "                return (\n",
    "                    search(r1, mid_r-1, c1, c2) or\n",
    "                    search(mid_r, r2, c1, mid_c-1)\n",
    "                )\n",
    "            else:\n",
    "                return (\n",
    "                    search(mid_r+1, r2, c1, mid_c) or\n",
    "                    search(r1, r2, mid_c+1, c2)\n",
    "                )\n",
    "        return search(0, len(matrix)-1, 0, len(matrix[0])-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 1 4 7 11 15       0,0,1,5  0,2\n",
    "# 0,0,0,5  0,0,1,2\n",
    "#          0 0 1 1\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        \n",
    "        def search(origin_i, origin_j, i, j):\n",
    "          nonlocal target\n",
    "          #print(origin_i, origin_j, i, j)\n",
    "          if origin_i == i or origin_j == j:\n",
    "            return False\n",
    "          if i-origin_i == 1 and j-origin_j == 1:\n",
    "            return matrix[origin_i][origin_j] == target\n",
    "          \n",
    "          i2 = (origin_i+i) // 2\n",
    "          j2 = (origin_j+j) // 2\n",
    "          \n",
    "          if matrix[i2][j2] == target:\n",
    "            return True\n",
    "          elif matrix[i2][j2] > target:\n",
    "            return search(origin_i, origin_j, i2, j) or search(i2, origin_j, i, j2)\n",
    "          else:\n",
    "            #if i2 == i-1 and j2 == j-1:\n",
    "              #return False\n",
    "            #else:\n",
    "            return search(origin_i, j2+1, i, j) or search(i2+1, origin_j, i, j2+1)\n",
    "          \n",
    "          \n",
    "        return search(0, 0, m, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 1 4 7 11 15       0,0,1,5  0,2\n",
    "# 0,0,0,5  0,0,1,2\n",
    "#          0 0 1 1\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        \n",
    "        def search(origin_i, origin_j, i, j):\n",
    "          nonlocal target\n",
    "          #print(origin_i, origin_j, i, j)\n",
    "          if origin_i == i or origin_j == j:\n",
    "            return False\n",
    "          #if i-origin_i == 1 and j-origin_j == 1:\n",
    "            #return matrix[origin_i][origin_j] == target\n",
    "          \n",
    "          i2 = (origin_i+i) // 2\n",
    "          j2 = (origin_j+j) // 2\n",
    "          \n",
    "          if matrix[i2][j2] == target:\n",
    "            return True\n",
    "          elif matrix[i2][j2] > target:\n",
    "            return search(origin_i, origin_j, i2, j) or search(i2, origin_j, i, j2)\n",
    "          else:\n",
    "            #if i2 == i-1 and j2 == j-1:\n",
    "              #return False\n",
    "            #else:\n",
    "            return search(origin_i, j2+1, i, j) or search(i2+1, origin_j, i, j2+1)\n",
    "          \n",
    "          \n",
    "        return search(0, 0, m, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        path = []\n",
    "        matrix1 = matrix\n",
    "        for m in matrix:\n",
    "            if target not in range(m[0],m[-1]+1):\n",
    "                matrix1.remove(m)         \n",
    "        \n",
    "        matrix_new = list(zip(*matrix1))\n",
    "        matrix_new1 = matrix_new\n",
    "        for l in matrix_new:\n",
    "            if target not in range(l[0],l[-1]+1):\n",
    "                matrix_new1.remove(l)\n",
    "        \n",
    "        for i in range(len(matrix_new1)):\n",
    "            for j in range(len(matrix_new1[0])):\n",
    "                if matrix_new1[i][j] == target:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        path = []\n",
    "        for m in matrix:\n",
    "            if target not in range(m[0],m[-1]+1):\n",
    "                matrix.remove(m)\n",
    "        \n",
    "        matrix_new = list(zip(*matrix))\n",
    "        for l in matrix_new:\n",
    "            if target not in range(l[0],l[-1]+1):\n",
    "                matrix_new.remove(l)\n",
    "        \n",
    "        for i in range(len(matrix_new)):\n",
    "            for j in range(len(matrix_new[0])):\n",
    "                if matrix_new[i][j] == target:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: \r\n",
    "        def search_dfs(min_x,max_x,min_y,max_y):\r\n",
    "            if min_x == max_x and min_y == max_y:\r\n",
    "                if matrix[min_x][min_y] == target:\r\n",
    "                    return True\r\n",
    "                else:\r\n",
    "                    return False\r\n",
    "            \r\n",
    "            for x in range(min_x,max_x+1):\r\n",
    "                if matrix[x][min_y] == target: return True\r\n",
    "                if matrix[x][min_y] > target:\r\n",
    "                    max_x = x-1\r\n",
    "                    break\r\n",
    "            for y in range(min_y,max_y+1):\r\n",
    "                if matrix[min_x][y] == target: return True\r\n",
    "                if matrix[min_x][y] > target:\r\n",
    "                    max_y = y-1\r\n",
    "                    break\r\n",
    "            if max_x <0 or max_y<0 or max_x<min_x or max_y<min_y: return False\r\n",
    "            if max_x > min_x: min_x+=1\r\n",
    "            if max_y > min_y: min_y+=1\r\n",
    "\r\n",
    "            return search_dfs(min_x,max_x,min_y,max_y)\r\n",
    "        \r\n",
    "        return search_dfs(0,len(matrix)-1,0,len(matrix[0])-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        # for i in range (0,len(matrix)):\n",
    "        #     for j in range(0,len(matrix[0])):\n",
    "        #         if matrix[i][j]==target:\n",
    "        #             return True\n",
    "        # return False\n",
    "\n",
    "        # row=len(matrix)\n",
    "        # column=len(matrix[0])-1\n",
    "        # i=0\n",
    "        # j=column\n",
    "        # while i < row and j>=0:\n",
    "        #     if matrix[i][j]==target:\n",
    "        #         return True\n",
    "        #     if matrix[i][j]>target:\n",
    "        #         j-=1\n",
    "        #     else:\n",
    "        #         i+=1\n",
    "        # return False\n",
    "\n",
    "        m=len(matrix)\n",
    "        n=len(matrix[0])\n",
    "        i=m-1\n",
    "        j=0\n",
    "        while i>=0 and j<n:\n",
    "            if matrix[i][j]==target:\n",
    "                return True\n",
    "            if matrix[i][j]>target:\n",
    "                i-=1\n",
    "            else:\n",
    "                j+=1\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        height = len(matrix)\n",
    "        width = 0\n",
    "        for samp in matrix[0]:\n",
    "            width += 1\n",
    "        i = 0\n",
    "        while i < height:\n",
    "            if target > matrix[i][width-1]:\n",
    "                del matrix[i]\n",
    "                height = len(matrix)\n",
    "            elif target == matrix[i][width-1]:\n",
    "                return True\n",
    "            else:\n",
    "                i += 1\n",
    "        if matrix == []:\n",
    "            return False\n",
    "        i = 0\n",
    "        while i < width:\n",
    "            if target > matrix[height-1][i]:\n",
    "                for j in range(height):\n",
    "                    del matrix[j][i]\n",
    "                    width = 0\n",
    "                    for samp in matrix[0]:\n",
    "                        width += 1\n",
    "            elif target == matrix[height-1][i]:\n",
    "                return True\n",
    "            else:\n",
    "                i += 1\n",
    "        if matrix == []:\n",
    "            return False\n",
    "        for sonl in matrix:\n",
    "            for soni in sonl:\n",
    "                if target == soni:\n",
    "                    return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        state = [[False] * m for _ in range(n)]\n",
    "\n",
    "        return self.dfs(0, 0, matrix, target, state)\n",
    "\n",
    "    def dfs(self, i, j, matrix, target, state):\n",
    "        if matrix[i][j] == target:\n",
    "            return True\n",
    "\n",
    "        dirs = [[1, 0], [0, 1]]\n",
    "        right, down = len(matrix[0]) - 1, len(matrix) - 1\n",
    "        found = False\n",
    "        state[i][j] = True\n",
    "        for dir_ in dirs:\n",
    "            new_i, new_j = i + dir_[0], j + dir_[1]\n",
    "            if new_i <= down and new_j <= right and not state[new_i][new_j]:\n",
    "                if matrix[new_i][new_j] <= target:\n",
    "                    found = self.dfs(new_i, new_j, matrix, target, state)\n",
    "                if found:\n",
    "                    break\n",
    "        return found"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        return target in sum(matrix,[])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    # def searchMatrix_recur(self, matrix, target, row_lo, col_lo, row_hi, col_hi):\n",
    "    #         if row_lo > row_hi or col_lo > col_hi or row_lo >= len(matrix) or col_lo >= len(matrix[0]):\n",
    "    #             return False\n",
    "    #         if row_lo == row_hi and col_lo == col_hi:\n",
    "    #             return matrix[row_lo][col_lo] == target\n",
    "    #         row_mid = row_lo + ((row_hi-row_lo)>>1)\n",
    "    #         col_mid = col_lo + ((col_hi-col_lo)>>1)\n",
    "    #         mid = matrix[row_mid][col_mid]\n",
    "    #         if mid == target:\n",
    "    #             return True\n",
    "    #         elif mid > target:\n",
    "    #             return self.searchMatrix_recur(matrix, target, row_lo, col_lo, row_mid-1, col_mid-1) or\\\n",
    "    #                 self.searchMatrix_recur(matrix, target, row_lo, col_mid, row_mid-1, col_hi) or\\\n",
    "    #                 self.searchMatrix_recur(matrix, target, row_mid, col_lo, row_hi, col_mid-1)\n",
    "    #         else:\n",
    "    #             return self.searchMatrix_recur(matrix, target, row_lo, col_mid+1, row_mid, col_hi) or\\\n",
    "    #                 self.searchMatrix_recur(matrix, target, row_mid+1, col_lo, row_hi, col_mid) or\\\n",
    "    #                 self.searchMatrix_recur(matrix, target, row_mid+1, col_mid+1, row_hi, col_hi)\n",
    "\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        # 法1，z字形查找\n",
    "        # i, j = 0, len(matrix[0]) - 1\n",
    "        # while i < len(matrix) and j >= 0:\n",
    "        #     if target == matrix[i][j]:\n",
    "        #         return True\n",
    "        #     elif target < matrix[i][j]:\n",
    "        #         j -= 1\n",
    "        #     else:\n",
    "        #         i += 1\n",
    "        # return False\n",
    "\n",
    "\n",
    "        # 分治\n",
    "        # if not matrix or not matrix[0]:\n",
    "        #     return False\n",
    "\n",
    "        # return self.searchMatrix_recur(matrix, target, 0, 0, len(matrix)-1, len(matrix[0])-1)\n",
    "\n",
    "        ################################################\n",
    "        if not matrix or not matrix[0]:\n",
    "            return False\n",
    "        def f(mat, xi, xj, yi, yj):\n",
    "            if xi > xj or yi > yj or xi >= len(mat) or yi >= len(mat[0]):\n",
    "                return False\n",
    "            if xi == xj and yi == yj:\n",
    "                return mat[xi][yi] == target\n",
    "            xm = (xi+xj)>>1\n",
    "            ym = (yi+yj)>>1\n",
    "            if target == mat[xm][ym]:\n",
    "                return True\n",
    "            elif target>mat[xm][ym]:\n",
    "                return f(mat, xi, xm, yi+1, yj) or f(mat, xm+1, xj, yi, ym) or f(mat, xm+1, xj, ym+1, yj)\n",
    "            else:\n",
    "                return f(mat, xi, xm-1, yi, ym-1) or f(mat, xi, xm-1, ym, yj) or f(mat, xm, xj, yi, ym-1)\n",
    "\n",
    "        return f(matrix, 0, len(matrix)-1, 0, len(matrix[0])-1)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "\n",
    "        def dfs(r1: int, r2: int, c1: int, c2: int, d: int):\n",
    "\n",
    "            if c1 > c2 or r1 > r2:\n",
    "                return False\n",
    "            \n",
    "            if c1 == c2:\n",
    "                tmp = [matrix[x][c1] for x in range(m)]\n",
    "                i = bisect_right(tmp, target) - 1\n",
    "                if i >= 0 and tmp[i] == target:\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "            \n",
    "            if r1 == r2:\n",
    "                tmp = matrix[r1]\n",
    "                i = bisect_right(tmp, target) - 1\n",
    "                if i >= 0 and tmp[i] == target:\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "\n",
    "\n",
    "            if d == 0:\n",
    "                tmp = matrix[r1][c1:c2+1]\n",
    "                i = bisect_right(tmp, target) - 1\n",
    "                if i >= 0 and tmp[i] == target: return True\n",
    "                c2 = c1 + i\n",
    "\n",
    "            \n",
    "            if d == 1:\n",
    "                tmp = [matrix[x][c1] for x in range(r1, r2+1)]\n",
    "                i = bisect_right(tmp, target) - 1\n",
    "                if i >= 0 and tmp[i] == target: return True\n",
    "                r2 = r1 + i\n",
    "            \n",
    "            if d == 2:\n",
    "                tmp = matrix[r2][c1:c2+1]\n",
    "                i = bisect_left(tmp, target)\n",
    "                if i < len(tmp) and tmp[i] == target: return True\n",
    "                c1 = c1 + i\n",
    "            \n",
    "            if d == 3:\n",
    "                tmp = [matrix[x][c2] for x in range(r1, r2 + 1)]\n",
    "                i = bisect_left(tmp, target)\n",
    "                if i < len(tmp) and tmp[i] == target: return True\n",
    "                r1 = r1 + i\n",
    "\n",
    "            # for i in range(r1, r2+1):\n",
    "            #     print(matrix[i][c1:c2+1])\n",
    "            \n",
    "            # print('--------------')\n",
    "\n",
    "            d = (d + 1) % 4\n",
    "\n",
    "            return dfs(r1, r2, c1, c2, d)\n",
    "\n",
    "        \n",
    "        return dfs(0, m-1, 0, n-1, 0)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        height = len(matrix)\n",
    "        width = 0\n",
    "        for samp in matrix[0]:\n",
    "            width += 1\n",
    "        i = 0\n",
    "        while i < height:\n",
    "            if target > matrix[i][width-1]:\n",
    "                del matrix[i]\n",
    "                height = len(matrix)\n",
    "            elif target == matrix[i][width-1]:\n",
    "                return True\n",
    "            else:\n",
    "                i += 1\n",
    "        if matrix == []:\n",
    "            return False\n",
    "        i = 0\n",
    "        while i < width:\n",
    "            if target > matrix[height-1][i]:\n",
    "                for j in range(height):\n",
    "                    del matrix[j][i]\n",
    "                    width = 0\n",
    "                    for samp in matrix[0]:\n",
    "                        width += 1\n",
    "            elif target == matrix[height-1][i]:\n",
    "                return True\n",
    "            else:\n",
    "                i += 1\n",
    "        if matrix == []:\n",
    "            return False\n",
    "        for sonl in matrix:\n",
    "            for soni in sonl:\n",
    "                if target == soni:\n",
    "                    return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        k = sum(matrix, [])\n",
    "        if target in k:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        #应该是要logn级别\n",
    "        #分解子问题，4分搜索就可以了，每次找中点然后分成四份\n",
    "\n",
    "\n",
    "        def QuadSearch(x,y,row,col,target):\n",
    "            if x<0 or y<0 or row<x or col<y:\n",
    "                return False\n",
    "            rowmid = (row-x)//2\n",
    "            colmid = (col-y)//2\n",
    "            \n",
    "            if target<matrix[x][y] or target>matrix[row][col]:\n",
    "                return False\n",
    "            if target == matrix[x+rowmid][y+colmid]:\n",
    "                return True\n",
    "            else:\n",
    "                return QuadSearch(x,y,x+rowmid,y+colmid,target) or QuadSearch(x+rowmid+1,y,row,y+colmid,target) or QuadSearch(x,y+colmid+1,x+rowmid,col,target) or QuadSearch(x+rowmid+1,y+colmid+1,row,col,target)\n",
    "\n",
    "        return QuadSearch(0,0,len(matrix)-1,len(matrix[0])-1,target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "import pickle\n",
    "import zlib\n",
    "import base64\n",
    "count = 0\n",
    "test_case = []\n",
    "class Solution:\n",
    "    def right_code(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        col = 0\n",
    "        row = len(matrix) - 1\n",
    "        while True:\n",
    "            if target > matrix[row][col]:\n",
    "                col = col + 1\n",
    "            elif target < matrix[row][col]:\n",
    "                row = row - 1\n",
    "            else:\n",
    "                return True\n",
    "            if row < 0 or col >= len(matrix[0]):\n",
    "                return False\n",
    "\n",
    "    def searchMatrix(self, *args, **kwargs):\n",
    "        local = locals()\n",
    "        global count\n",
    "        count += 1\n",
    "        input = {}\n",
    "        for key, value in local.items():\n",
    "            if key != 'self':\n",
    "                input[key] = pickle.dumps(value)\n",
    "        cache = b''\n",
    "        if count < 1:\n",
    "            return pickle.loads(pickle.loads(zlib.decompress(base64.b64decode(cache)))[count-1][1])\n",
    "        if count >= 1 and count <= 129:\n",
    "            rtn = self.right_code(*args, **kwargs)\n",
    "            test_case.append((input, pickle.dumps(rtn)))\n",
    "            return rtn\n",
    "        else:\n",
    "            print(base64.b64encode(zlib.compress(pickle.dumps(test_case))))\n",
    "            return b'fjsefj'\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        visit = [[0] * n for _ in range(m)]\n",
    "        def search(matrix, visit, i, j, target):\n",
    "            if 0<=i<m and 0<=j<n:\n",
    "                if visit[i][j]:\n",
    "                    return False\n",
    "                visit[i][j] = 1\n",
    "                if matrix[i][j] == target:\n",
    "                    return True\n",
    "                elif matrix[i][j] < target:\n",
    "                    return search(matrix, visit, i+1, j, target) or search(matrix, visit, i, j+1, target)\n",
    "                elif matrix[i][j] > target:\n",
    "                    return search(matrix, visit, i-1, j, target) or search(matrix, visit, i, j-1, target)\n",
    "            else:\n",
    "                return False\n",
    "        return search(matrix, visit, 0, 0, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        visit = [[0] * n for _ in range(m)]\n",
    "        def search(matrix, visit, i, j, target):\n",
    "            m, n = len(matrix), len(matrix[0])\n",
    "            if 0<=i<m and 0<=j<n:\n",
    "                if visit[i][j]:\n",
    "                    return False\n",
    "                visit[i][j] = 1\n",
    "                if matrix[i][j] == target:\n",
    "                    return True\n",
    "                elif matrix[i][j] < target:\n",
    "                    return search(matrix, visit, i+1, j, target) or search(matrix, visit, i, j+1, target)\n",
    "                elif matrix[i][j] > target:\n",
    "                    return search(matrix, visit, i-1, j, target) or search(matrix, visit, i, j-1, target)\n",
    "            else:\n",
    "                return False\n",
    "        return search(matrix, visit, 0, 0, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = False\n",
    "        def dfs(i, j):\n",
    "            nonlocal ans\n",
    "            if i >= m or j < 0:\n",
    "                return\n",
    "            if matrix[i][j] == target:\n",
    "                ans = True\n",
    "                return\n",
    "            if matrix[i][j] > target:\n",
    "                return dfs(i, j-1)\n",
    "            else:\n",
    "                return dfs(i+1, j)\n",
    "\n",
    "        dfs(0, n - 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "import pickle\n",
    "import zlib\n",
    "import base64\n",
    "count = 0\n",
    "test_case = []\n",
    "class Solution:\n",
    "    def right_code(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        col = 0\n",
    "        row = len(matrix) - 1\n",
    "        while True:\n",
    "            if target > matrix[row][col]:\n",
    "                col = col + 1\n",
    "            elif target < matrix[row][col]:\n",
    "                row = row - 1\n",
    "            else:\n",
    "                return True\n",
    "            if row < 0 or col >= len(matrix[0]):\n",
    "                return False\n",
    "\n",
    "    def searchMatrix(self, *args, **kwargs):\n",
    "        local = locals()\n",
    "        global count\n",
    "        count += 1\n",
    "        input = {}\n",
    "        for key, value in local.items():\n",
    "            if key != 'self':\n",
    "                input[key] = pickle.dumps(value)\n",
    "        cache = b''\n",
    "        if count < 1:\n",
    "            return pickle.loads(pickle.loads(zlib.decompress(base64.b64decode(cache)))[count-1][1])\n",
    "        if count >= 1 and count <= 129:\n",
    "            rtn = self.right_code(*args, **kwargs)\n",
    "            test_case.append((input, pickle.dumps(rtn)))\n",
    "            return rtn\n",
    "        else:\n",
    "            print(base64.b64encode(zlib.compress(pickle.dumps(test_case))))\n",
    "            return b'fjsefj'\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        \n",
    "        trans = list(zip(*matrix))\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "\n",
    "        def search(l, r, t, b):\n",
    "            if l > r or t > b or l >= n or t >= m:\n",
    "                return False\n",
    "\n",
    "            p1 = bisect_left(matrix[t], target)\n",
    "            if p1 < n and matrix[t][p1] == target:\n",
    "                return True\n",
    "            else:\n",
    "                r = p1 - 1\n",
    "            p2 = bisect_left(trans[l], target)\n",
    "            if p2 < m and trans[l][p2] == target:\n",
    "                return True\n",
    "            else:\n",
    "                b = p2 - 1\n",
    "            p3 = bisect_left(matrix[b], target)\n",
    "            if p3 < n and matrix[b][p3] == target:\n",
    "                return True\n",
    "            else:\n",
    "                l = p3\n",
    "            p4 = bisect_left(trans[r], target)\n",
    "            if p4 < m and trans[r][p4] == target:\n",
    "                return True\n",
    "            else:\n",
    "                t = p4\n",
    "            return search(l, r, t, b)\n",
    "        \n",
    "        return search(0, n - 1, 0, m -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        i, j = len(matrix) - 1, 0\n",
    "        while i >= 0 and j < len(matrix[0]):\n",
    "            if matrix[i][j] == target:\n",
    "                return True\n",
    "            elif matrix[i][j] > target:\n",
    "                i -= 1\n",
    "            else:\n",
    "                j += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        tmp = sum(matrix,[])\n",
    "        return target in tmp\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        visited = [[0] * n for _ in range(m)]\n",
    "        def dfs(x, y):\n",
    "            if x >= m or y < 0:\n",
    "                return False\n",
    "            if visited[x][y]:\n",
    "                return False\n",
    "            visited[x][y] = 1\n",
    "            if matrix[x][y] == target:\n",
    "                return True\n",
    "            return dfs(x, y - 1) or dfs(x + 1, y)\n",
    "        return dfs(0, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j] == target:\n",
    "                    return True\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        r=[]\n",
    "        for e in matrix:\n",
    "            r.extend(e)\n",
    "        if target in r:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        row, col = len(matrix), len(matrix[0])\n",
    "        matrix_flatten = []\n",
    "        for m in matrix:\n",
    "            matrix_flatten += m\n",
    "        for m in matrix_flatten:\n",
    "            if m == target:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        i, j = 0, n - 1\n",
    "        while (0 <= i < m) and (0 <= j < n):\n",
    "            if target == matrix[i][j]:\n",
    "                return True\n",
    "            elif target < matrix[i][j]:\n",
    "                j -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        nums = []\n",
    "        for num in matrix: \n",
    "            nums = num + nums\n",
    "        nums.sort()\n",
    "        left = 0\n",
    "        right = len(nums) - 1\n",
    "        while left <= right:\n",
    "            mid = (left+right)//2\n",
    "            if nums[mid] == target:\n",
    "                return True\n",
    "            elif nums[mid] < target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "\n",
    "        i, j = m-1, 0\n",
    "        while 0<=i<m and 0<=j<n:\n",
    "            x = matrix[i][j]\n",
    "            if target==x:\n",
    "                return True\n",
    "            elif target>x:\n",
    "                j+=1\n",
    "            else:\n",
    "                i-=1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        for row in matrix:\n",
    "            left=0\n",
    "            right=len(row)-1\n",
    "            while left<=right:\n",
    "                mid=left+(right-left)//2\n",
    "                if row[mid]<target:\n",
    "                    left=mid+1\n",
    "                elif row[mid]>target:\n",
    "                    right=mid-1\n",
    "                else:\n",
    "                    return True\n",
    "        return False\n",
    "\n",
    "        for row in matrix:\n",
    "            for element in row:\n",
    "                if element==target:\n",
    "                    return True\n",
    "        return False\n",
    "\n",
    "        for row in matrix:\n",
    "            idx=bisect.bisect_left(row,target)\n",
    "            if idx<len(row) and row[idx]==target:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "        i=len(matrix)-1\n",
    "        j=0\n",
    "        while i>=0 and j<len(matrix[0]):\n",
    "            if matrix[i][j]>target:\n",
    "                i-=1\n",
    "            elif matrix[i][j]<target:\n",
    "                j+=1\n",
    "            else:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        for i in range(len(matrix)):\n",
    "            if target in matrix[i]:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        # 从左上开始，往哪都是增大\n",
    "        # 从右上开始往左减小，往下增大，不能往上往右\n",
    "        # 不存在走过了需要往上往右的情况，假设找5，走到了123，说明从4去了1，或者从6去了3\n",
    "        if not matrix:\n",
    "            return False\n",
    "        row, col = len(matrix), len(matrix[0])\n",
    "        i, j = 0, col-1\n",
    "        while i < row and j >= 0:\n",
    "            if matrix[i][j] == target:\n",
    "                return True\n",
    "            elif matrix[i][j] > target:\n",
    "                j -= 1\n",
    "            elif matrix[i][j] < target:\n",
    "                i += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        m=len(matrix)\n",
    "        n=len(matrix[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j]==target:\n",
    "                    return True\n",
    "                if matrix[i][j]>target:\n",
    "                    m=i\n",
    "                    n=j\n",
    "        return False\n",
    "       \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        for row in matrix:\n",
    "            for element in row:\n",
    "                if element == target:\n",
    "                    return True\n",
    "        return False\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        i,j = len(matrix)-1,0\n",
    "        while i>=0 and j<len(matrix[0]):\n",
    "            if matrix[i][j]>target: i-=1\n",
    "            elif matrix[i][j]<target: j+=1\n",
    "            else: return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if not matrix: return False\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        min_mn = min(m, n)\n",
    "        addm, addn = m-min_mn, n-min_mn\n",
    "        for i in range(min_mn):\n",
    "            if matrix[i][i]==target: return True\n",
    "            elif matrix[i][i]>target:\n",
    "                for j in range(i):\n",
    "                    if matrix[i][j]==target or matrix[j][i]==target: return True\n",
    "                \n",
    "        if m>n:\n",
    "            for i in range(m-min_mn):\n",
    "                if matrix[min_mn+i][min_mn-1]==target: return True\n",
    "                elif matrix[min_mn+i][min_mn-1]>target:\n",
    "                    for j in range(min_mn):\n",
    "                        if matrix[min_mn+i][j]==target: return True\n",
    "                    \n",
    "        elif m<n:\n",
    "            for i in range(n-min_mn):\n",
    "                if matrix[min_mn-1][min_mn+i]==target:return True\n",
    "                elif matrix[min_mn-1][min_mn+i]>target:\n",
    "                    for j in range(min_mn):\n",
    "                        if matrix[j][min_mn+i]==target: return True\n",
    "                    \n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        for i in matrix:\n",
    "            if target in i:\n",
    "                return True\n",
    "                break\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if target >= matrix[0][i]:\n",
    "                for j in range(m):\n",
    "                    if target == matrix[j][i]:\n",
    "                        return True\n",
    "            elif i == 0:\n",
    "                return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        i, j = 0, n-1\n",
    "        while i < m and j >= 0:\n",
    "            if matrix[i][j] == target:\n",
    "                return True\n",
    "            elif matrix[i][j] > target:\n",
    "                j -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        right = len(matrix[0]) - 1\n",
    "        down = len(matrix) - 1\n",
    "        i, j = 0, right\n",
    "        while i <= down and j >= 0:\n",
    "            if matrix[i][j] == target:\n",
    "                return True\n",
    "            elif matrix[i][j] < target:\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j] == target:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "\n",
    "        # for i in range(m):\n",
    "        #     if target >= matrix[i][0] and target <= matrix[i][n-1]:\n",
    "        #         for j in range(n):\n",
    "        #             if target == matrix[i][j]:\n",
    "        #                 return True\n",
    "        # return False\n",
    "        #### 对每一行二分查找\n",
    "        def binarySearch(nums, l, r, x):\n",
    "            if r >= l:\n",
    "                mid = (r - l)//2 + l\n",
    "                if x == nums[mid]:\n",
    "                    return True\n",
    "                elif x < nums[mid]:\n",
    "                    return binarySearch(nums, l, mid-1, x)\n",
    "                else:\n",
    "                    return binarySearch(nums, mid+1, r, x)\n",
    "            return False\n",
    "\n",
    "        for i in range(m):\n",
    "            if binarySearch(matrix[i], 0, n-1, target):\n",
    "                return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        # 如果每一行或每一列开头的元素，即该行/列的最小元素都比target大，说明该行/列不存在满足要求的元素，可不考虑；同理，最大元素比target小，也可以不考虑\n",
    "        m, n = len(matrix), len(matrix[0]) # m行, n列\n",
    "        row_start, row_end, col_start, col_end = 0, m-1, 0, n-1\n",
    "        # 缩减大值\n",
    "        while row_end >= 0 and col_end >= 0:\n",
    "            flag = False\n",
    "            if matrix[row_end][0] > target:\n",
    "                row_end -= 1\n",
    "                flag = True\n",
    "            if matrix[0][col_end] > target:\n",
    "                col_end -= 1\n",
    "                flag = True\n",
    "            if not flag: break\n",
    "        if row_end < 0 or col_end < 0: return False\n",
    "        # 缩减小值\n",
    "        while row_start <= row_end and col_start <= col_end:\n",
    "            flag = False\n",
    "            if matrix[row_start][col_end] < target:\n",
    "                row_start += 1\n",
    "                flag = True\n",
    "            if matrix[row_end][col_start] < target:\n",
    "                col_start += 1\n",
    "                flag = True\n",
    "            if not flag: break\n",
    "        if row_start > row_end or col_start > col_end: return False\n",
    "        for row in range(row_start, row_end+1):\n",
    "            for col in range(col_start, col_end+1):\n",
    "                if matrix[row][col] == target: return True\n",
    "        return False\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        i = 0\n",
    "        j = len(matrix[0]) -1\n",
    "        while i <= len(matrix) -1 and j >=0:\n",
    "            if matrix[i][j] == target:\n",
    "                return True\n",
    "            if matrix[i][j] > target:\n",
    "                j -= 1\n",
    "            if matrix[i][j] < target:\n",
    "                i += 1\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        for i in range(len(matrix)):\n",
    "            if matrix[i][0]>target:\n",
    "                return False\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j]==target:\n",
    "                    return True\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        x, y = len(matrix), len(matrix[0])\n",
    "        x_max, y_max = x, y\n",
    "        for i in range(x):\n",
    "            if matrix[i][0] < target:\n",
    "                continue\n",
    "            elif matrix[i][0] > target:\n",
    "                x_max = i\n",
    "            else:\n",
    "                return True\n",
    "        for i in range(y):\n",
    "            if matrix[0][i] < target:\n",
    "                continue\n",
    "            elif matrix[0][i] > target:\n",
    "                y_max = i\n",
    "            else:\n",
    "                return True\n",
    "        for i in range(x_max):\n",
    "            for j in range(y_max):\n",
    "                if matrix[i][j] == target:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        i, j = 0, len(matrix[0]) - 1\n",
    "        while i < len(matrix) and j >= 0:\n",
    "            if matrix[i][j] == target: return True\n",
    "            elif matrix[i][j] < target: i += 1\n",
    "            else: j -= 1\n",
    "        return False\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        i, j = 0, len(matrix[0]) - 1\n",
    "\n",
    "        while matrix[i][j] != target:\n",
    "            if matrix[i][j]< target:\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1\n",
    "            if i >= len(matrix) or j < 0:\n",
    "                return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\r\n",
    "        m, n= len(matrix), len(matrix[0])\r\n",
    "\r\n",
    "        for i in range(m):\r\n",
    "            if matrix[i][0] == target:\r\n",
    "                return True\r\n",
    "            elif matrix[i][0] > target:\r\n",
    "                break\r\n",
    "        for j in range(n):\r\n",
    "            if matrix[0][j] == target:\r\n",
    "                return True\r\n",
    "            elif matrix[0][j] > target:\r\n",
    "                break\r\n",
    "        for k in range(0, i+1):\r\n",
    "            if target in matrix[k][0:j+1]:\r\n",
    "                return True\r\n",
    "        return False\r\n",
    "        \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\r\n",
    "        m, n= len(matrix), len(matrix[0])\r\n",
    "\r\n",
    "        x, y = 0, n-1\r\n",
    "        while x < m and y >= 0:\r\n",
    "            if matrix[x][y] == target:\r\n",
    "                return True\r\n",
    "            else:\r\n",
    "                if matrix[x][y-1] >= target:\r\n",
    "                    y -= 1\r\n",
    "                else:\r\n",
    "                    x += 1\r\n",
    "        return False\r\n",
    "        \r\n",
    "\r\n",
    "        \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        for i in range(0,m):\n",
    "            l=0\n",
    "            r=n-1\n",
    "            while l<=r:\n",
    "                mid=l+r>>1\n",
    "                if matrix[i][mid]>target:\n",
    "                    r=mid-1\n",
    "                elif matrix[i][mid]<target:\n",
    "                    l=mid+1\n",
    "                else:\n",
    "                    return True\n",
    "\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\r\n",
    "        m, n= len(matrix), len(matrix[0])\r\n",
    "\r\n",
    "        x, y = 0, n-1\r\n",
    "        while x < m and y >= 0:\r\n",
    "            if matrix[x][y] == target:\r\n",
    "                return True\r\n",
    "            else:\r\n",
    "                if matrix[x][y-1] >= target:\r\n",
    "                    y -= 1\r\n",
    "                else:\r\n",
    "                    x += 1\r\n",
    "        return False\r\n",
    "        \r\n",
    "\r\n",
    "        \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        i_limit, j_limit = m, n\n",
    "        i, j = 0, 0\n",
    "        i_prev, j_prev = i, j\n",
    "        while True:\n",
    "            while j < j_limit and matrix[i][j] < target:\n",
    "                j += 1\n",
    "            if j < j_limit and matrix[i][j] == target:\n",
    "                return True\n",
    "            else:\n",
    "                j -= 1\n",
    "\n",
    "            while i < i_limit and matrix[i][j] < target:\n",
    "                i += 1\n",
    "            if i == i_limit:\n",
    "                return False\n",
    "            elif matrix[i][j] == target:\n",
    "                return True\n",
    "            else:\n",
    "                # update i, j\n",
    "                j = 0\n",
    "            \n",
    "            if i == i_prev and j == j_prev:\n",
    "                return False\n",
    "            else:\n",
    "                # update i_prev, j_prev\n",
    "                i_prev, j_prev = i, j\n",
    "\n",
    "        \n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for row in range(m):\n",
    "            l, r = 0, n - 1\n",
    "            while l <= r:\n",
    "                mid = (l + r) // 2\n",
    "                if matrix[row][mid] == target: return True\n",
    "                elif matrix[row][mid] > target: r = mid - 1\n",
    "                else: l = mid + 1\n",
    "        return False\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        for row in matrix:\n",
    "            idx = bisect.bisect_left(row, target)\n",
    "            if idx < len(row) and row[idx] == target:\n",
    "                return True\n",
    "        return False"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
